# 给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。 
# 
#  子数组是数组中元素的连续非空序列。 
# 
#  
# 
#  示例 1： 
# 
#  
# 输入：nums = [1,1,1], k = 2
# 输出：2
#  
# 
#  示例 2： 
# 
#  
# 输入：nums = [1,2,3], k = 3
# 输出：2
#  
# 
#  
# 
#  提示： 
# 
#  
#  1 <= nums.length <= 2 * 10⁴ 
#  -1000 <= nums[i] <= 1000 
#  -10⁷ <= k <= 10⁷ 
#  
# 
#  Related Topics 数组 哈希表 前缀和 👍 2577 👎 0
from typing import List


# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        """
        此方法时间复杂度太高
        :param nums:
        :param k:
        :return:
        d = {}
        l = len(nums)
        for i in range(l):
            temp = 0
            for j in range(i, l):
                temp += nums[j]
                d[temp] = d.get(temp, 0) + 1
        return d.setdefault(k, 0)
        """
        # 先把0放入字典
        d = {0: 1}
        temp = 0
        count = 0
        for i in range(len(nums)):
            temp += nums[i]
            if d.get(temp - k):
                count += d[temp-k]
            d[temp] = d.get(temp, 0) + 1
        return count


# leetcode submit region end(Prohibit modification and deletion)
print(Solution().subarraySum(nums=[1], k=0))
